package com.example.demo.leetcode.classics150;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _113环形子数组的最大和
 * @description
 * @date 2023/08/14 20:59
 * <p>
 * ******************************************************
 */
public class _113环形子数组的最大和 {

    /**
     * @ program: leet-code
     * @ description: 918.环形子数组的最大和
     * 根据题解可知：
     * 环形子数组的最大和具有两种可能，一种是不使用环的情况，另一种是使用环的情况
     * 不使用环的情况时，直接通过53题的思路，逐步求出整个数组中的最大子序和即可
     * 使用到了环，则必定包含 A[n-1]和 A[0]两个元素且说明从A[1]到A[n-2]这个子数组中必定包含负数
     * 【否则只通过一趟最大子序和就可以的出结果】
     * 因此只需要把A[1]-A[n-2]间这些负数的最小和求出来
     * 用整个数组的和 sum减掉这个负数最小和即可实现原环型数组的最大和
     * @ author: zhihua li
     * @ create: 2021-04-14 16:14
     **/
    public int maxSubarraySumCircular(int[] A) {
        int[] dp = new int[A.length];   //dp[i]用来记录以nums[i]结尾的最大子序列和
        dp[0] = A[0];                   //初始化dp
        int max = dp[0];                //最大子序列和
        int sum = dp[0];                //整个数组的和

        // 求最大子序列和，见53题
        for (int i = 1; i < dp.length; i++) {
            sum += A[i];
            dp[i] = A[i] + Math.max(dp[i - 1], 0);
            max = Math.max(dp[i], max);
        }

        int min = 0;    //开始求A[1]~A[n-1]上的最小子序列和
        for (int i = 1; i < dp.length - 1; i++) {
            dp[i] = A[i] + Math.min(0, dp[i - 1]);
            min = Math.min(dp[i], min);
        }
        return Math.max(sum - min, max);
    }


    public int maxSubarraySumCircular1(int[] nums) {
        int[] maxDp = new int[nums.length];
        int max = nums[0];
        maxDp[0] = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxDp[i] = maxDp[i - 1] > 0 ? maxDp[i - 1] + nums[i] : nums[i];
            max = Math.max(maxDp[i], max);
            sum += nums[i];
        }

        int[] minDp = new int[nums.length];
        int min = 0;
        for (int i = 1; i < nums.length - 1; i++) {
            minDp[i] = minDp[i - 1] > 0 ? nums[i] : minDp[i - 1] + nums[i];
            min = Math.min(minDp[i], min);
        }

        return Math.max(sum - min, max);
    }
}